{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Valid Arrangement of Pairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #graph #eulerian-circuit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #图 #欧拉回路"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: validArrangement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #合法重新排列数对"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的二维整数数组&nbsp;<code>pairs</code>&nbsp;，其中&nbsp;<code>pairs[i] = [start<sub>i</sub>, end<sub>i</sub>]</code>&nbsp;。如果 <code>pairs</code>&nbsp;的一个重新排列，满足对每一个下标 <code>i</code> （&nbsp;<code>1 &lt;= i &lt; pairs.length</code>&nbsp;）都有&nbsp;<code>end<sub>i-1</sub> == start<sub>i</sub></code><sub> </sub>，那么我们就认为这个重新排列是&nbsp;<code>pairs</code> 的一个 <strong>合法重新排列</strong> 。</p>\n",
    "\n",
    "<p>请你返回 <strong>任意一个</strong>&nbsp;<code>pairs</code> 的合法重新排列。</p>\n",
    "\n",
    "<p><b>注意：</b>数据保证至少存在一个 <code>pairs</code>&nbsp;的合法重新排列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>pairs = [[5,1],[4,5],[11,9],[9,4]]\n",
    "<b>输出：</b>[[11,9],[9,4],[4,5],[5,1]]\n",
    "<strong>解释：\n",
    "</strong>输出的是一个合法重新排列，因为每一个 end<sub>i-1</sub> 都等于 start<sub>i</sub>&nbsp;。\n",
    "end<sub>0</sub> = 9 == 9 = start<sub>1</sub> \n",
    "end<sub>1</sub> = 4 == 4 = start<sub>2</sub>\n",
    "end<sub>2</sub> = 5 == 5 = start<sub>3</sub>\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>pairs = [[1,3],[3,2],[2,1]]\n",
    "<b>输出：</b>[[1,3],[3,2],[2,1]]\n",
    "<strong>解释：</strong>\n",
    "输出的是一个合法重新排列，因为每一个 end<sub>i-1</sub> 都等于 start<sub>i</sub>&nbsp;。\n",
    "end<sub>0</sub> = 3 == 3 = start<sub>1</sub>\n",
    "end<sub>1</sub> = 2 == 2 = start<sub>2</sub>\n",
    "重新排列后的数组 [[2,1],[1,3],[3,2]] 和 [[3,2],[2,1],[1,3]] 都是合法的。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>pairs = [[1,2],[1,3],[2,1]]\n",
    "<b>输出：</b>[[1,2],[2,1],[1,3]]\n",
    "<strong>解释：</strong>\n",
    "输出的是一个合法重新排列，因为每一个 end<sub>i-1</sub> 都等于 start<sub>i</sub>&nbsp;。\n",
    "end<sub>0</sub> = 2 == 2 = start<sub>1</sub>\n",
    "end<sub>1</sub> = 1 == 1 = start<sub>2</sub>\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= pairs.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>pairs[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= start<sub>i</sub>, end<sub>i</sub> &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>start<sub>i</sub> != end<sub>i</sub></code></li>\n",
    "\t<li><code>pairs</code>&nbsp;中不存在一模一样的数对。</li>\n",
    "\t<li>至少 <strong>存在</strong> 一个合法的&nbsp;<code>pairs</code>&nbsp;重新排列。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [valid-arrangement-of-pairs](https://leetcode.cn/problems/valid-arrangement-of-pairs/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [valid-arrangement-of-pairs](https://leetcode.cn/problems/valid-arrangement-of-pairs/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[5,1],[4,5],[11,9],[9,4]]', '[[1,3],[3,2],[2,1]]', '[[1,2],[1,3],[2,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DirectedEulerPath:\n",
    "    def __init__(self, n, pairs):\n",
    "        # 数组形式存储的有向连接关系\n",
    "        self.n = n\n",
    "        self.pairs = pairs\n",
    "        # 欧拉路径上的每条边和经过的几点\n",
    "        self.paths = list()\n",
    "        self.nodes = list()\n",
    "        self.exist = False\n",
    "        self.get_euler_path()\n",
    "        return\n",
    "\n",
    "    def get_euler_path(self):\n",
    "        # 存顶点的出入度\n",
    "        degree = [0]*self.n\n",
    "        # 存储图关系\n",
    "        edge = [[] for _ in range(self.n)]\n",
    "        for i, j in self.pairs:\n",
    "            degree[i] += 1\n",
    "            degree[j] -= 1\n",
    "            edge[i].append(j)\n",
    "\n",
    "        # 根据字典序优先访问较小的\n",
    "        for i in range(self.n):\n",
    "            edge[i].sort(reverse=True)\n",
    "\n",
    "        # 寻找起始节点\n",
    "        starts = []\n",
    "        ends = []\n",
    "        zero = 0\n",
    "        for i in range(self.n):\n",
    "            if degree[i] == 1:\n",
    "                starts.append(i)\n",
    "            elif degree[i] == -1:\n",
    "                ends.append(i)\n",
    "            else:\n",
    "                zero += 1\n",
    "        del degree\n",
    "\n",
    "        # 图中恰好存在 1 个点出度比入度多 1（这个点即为起点） 1 个点出度比入度少 1（这个点即为终点）其余相等\n",
    "        if not len(starts) == len(ends) == 1:\n",
    "            if zero != self.n:\n",
    "                return\n",
    "            starts = [0]\n",
    "\n",
    "        # 使用迭代版本的Hierholzer算法\n",
    "        stack = [starts[0]]\n",
    "        while stack:\n",
    "            current = stack[-1]\n",
    "            if edge[current]:\n",
    "                next_node = edge[current].pop()\n",
    "                stack.append(next_node)\n",
    "            else:\n",
    "                self.nodes.append(current)\n",
    "                if len(stack) > 1:\n",
    "                    self.paths.append([stack[-2], current])\n",
    "                stack.pop()\n",
    "        self.paths.reverse()\n",
    "        self.nodes.reverse()\n",
    "        \"\"\"\n",
    "        改进前的深搜版本\n",
    "        def dfs(pre):\n",
    "            # 使用深度优先搜索（Hierholzer算法）求解欧拉通路\n",
    "            while edge[pre]:\n",
    "                nex = edge[pre].pop()\n",
    "                dfs(nex)\n",
    "                self.nodes.append(nex)\n",
    "                self.paths.append([pre, nex])\n",
    "            return\n",
    "\n",
    "        dfs(starts[0])\n",
    "        self.paths.reverse()\n",
    "        self.nodes.append(starts[0])\n",
    "        self.nodes.reverse()\n",
    "        \"\"\"\n",
    "        # 注意判断所有边都经过的才算欧拉路径\n",
    "        if len(self.nodes) == len(self.pairs) + 1:\n",
    "            self.exist = True\n",
    "        return\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:\n",
    "        nodes = set()\n",
    "        for a, b in pairs:\n",
    "            nodes.add(a)\n",
    "            nodes.add(b)\n",
    "        nodes = sorted(nodes)\n",
    "        ind = {num: i for i, num in enumerate(nodes)}\n",
    "        n = len(nodes)\n",
    "        eu =DirectedEulerPath(n, [[ind[a], ind[b]] for a, b in pairs])\n",
    "        return [[nodes[a], nodes[b]] for a, b in eu.paths]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validArrangement(self, pairs: [[int]]) -> [[int]]:\n",
    "        fa = defaultdict(list)\n",
    "        start = defaultdict(int)\n",
    "        end = defaultdict(int)\n",
    "        for s, e in pairs:\n",
    "            fa[s].append(e)\n",
    "            start[s] += 1\n",
    "            end[e] += 1\n",
    "        for k, v in fa.items():\n",
    "            v = Counter(v)\n",
    "            nums = [[-v1, k1] for k1, v1 in v.items()]\n",
    "            heapq.heapify(nums)\n",
    "            fa[k] = nums\n",
    "        def createPath(n):\n",
    "            s = -1\n",
    "            for k, v in start.items():\n",
    "                s =  k\n",
    "                if v - end[k] == 1:\n",
    "                   \n",
    "                    break\n",
    "                \n",
    "      \n",
    "            ans1 = []\n",
    "            n = len(pairs)\n",
    "            for _ in range(n):\n",
    "                if fa[s]:\n",
    "                    cnt, e = heapq.heappop(fa[s])\n",
    "                    if cnt != 0:\n",
    "                        cnt += 1\n",
    "                        ans1.append([s, e])\n",
    "                        start[s] -= 1\n",
    "                        end[e] -= 1\n",
    "                        if start[s] == 0:\n",
    "                            del start[s]\n",
    "                        if end[e] == 0:\n",
    "                            del end[e]\n",
    "                        s = e\n",
    "                        if cnt != 0:\n",
    "                            heapq.heappush(fa[s], [cnt, e])\n",
    "                else:\n",
    "                    del fa[s]\n",
    "            return ans1\n",
    "        def merge(nums1, nums2):\n",
    "            if not nums2:\n",
    "                return nums1\n",
    "            if not nums1:\n",
    "                return nums2\n",
    "            n1, n2 = len(nums1), len(nums2)\n",
    "            s1, e1 = nums1[0][0], nums1[-1][-1]\n",
    "            s2, e2 = nums2[0][0], nums2[-1][-1]\n",
    "            graph = defaultdict(set)\n",
    "            pos = {}\n",
    "            if s2 == e2:\n",
    "                for i in range(n2):\n",
    "                    graph[(nums2[i][0], nums2[i-1][-1])] = i\n",
    "                for i in range(1, n1):\n",
    "                    if (nums1[i][0], nums1[i-1][1]) in graph:\n",
    "                        idx = graph[(nums1[i][0], nums1[i-1][1])]\n",
    "                        ret = nums1[:i] + nums2[idx:] + nums2[:idx] + nums1[i:]\n",
    "                        return ret\n",
    "            if s1 == e1:\n",
    "                for i in range(n1):\n",
    "                    graph[(nums1[i][0], nums1[i-1][-1])] = i\n",
    "                for i in range(1, n2):\n",
    "                    if (nums2[i][0], nums2[i-1][1]) in graph:\n",
    "                        idx = graph[(nums2[i][0], nums2[i-1][1])]\n",
    "                        ret = nums2[:i] + nums1[idx:] + nums1[:idx] + nums2[i:]\n",
    "                        return ret\n",
    "            if nums1[0][0] == nums2[-1][-1]:\n",
    "                return nums2 + nums1\n",
    "            elif nums1[-1][-1] == nums2[0][0]:\n",
    "                return nums1 + nums2\n",
    "            for i in range(1, n1):\n",
    "                if nums1[i-1][1] == s2 and nums1[i][0] == e2:\n",
    "                    return nums1[:i] + nums2 + nums1[i:]\n",
    "            for i in range(1, n2):\n",
    "                if nums2[i-1][1] == s1 and nums2[i][0] == e1:\n",
    "                    return nums2[:i] + nums1 + nums2[i:]\n",
    "\n",
    "        n = len(pairs)\n",
    "        ans = createPath(n)\n",
    "        while len(ans) < n:\n",
    "            ans1 = createPath(n - len(ans))\n",
    "            ans = merge(ans, ans1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        cnt=Counter()\n",
    "        g=defaultdict(list)\n",
    "        for u,v in pairs:\n",
    "            cnt[u]+=1\n",
    "            cnt[v]-=1\n",
    "            g[u].append(v)\n",
    "        \n",
    "        start=None\n",
    "        for k,v in cnt.items():\n",
    "            start=k\n",
    "            if v==1:break\n",
    "        \n",
    "        def dfs(u):\n",
    "            while g[u]:\n",
    "                dfs(g[u].pop())\n",
    "            res.append(u)\n",
    "        res=[]\n",
    "        dfs(start)\n",
    "        print(res)\n",
    "        n=len(res)\n",
    "        res=res[::-1]\n",
    "        return [[res[i],res[i+1]] for i in range(n-1)]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:\n",
    "        vec = defaultdict(list)\n",
    "        indeg, outdeg = Counter(), Counter()\n",
    "        for k, v in pairs:\n",
    "            vec[k].append(v)\n",
    "            indeg[v] += 1\n",
    "            outdeg[k] += 1\n",
    "\n",
    "        start = pairs[0][0]\n",
    "        for k, _ in pairs:\n",
    "            if indeg[k] + 1 == outdeg[k]:\n",
    "                start = k\n",
    "                break\n",
    "\n",
    "        def dfs(cur):\n",
    "            while vec[cur]:\n",
    "                temp = heappop(vec[cur])\n",
    "                dfs(temp)\n",
    "                res.append([cur, temp])\n",
    "        res = []\n",
    "        dfs(start)\n",
    "        return res[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:           \n",
    "        def dfs(node):\n",
    "            v=nes[node]\n",
    "            while len(v):\n",
    "                dfs(v.pop())\n",
    "            rs.append(node)    \n",
    "        rs=[]\n",
    "        zy=defaultdict(int)\n",
    "        nes=defaultdict(list)\n",
    "        for p0,p1 in pairs:\n",
    "            zy[p0]+=1\n",
    "            zy[p1]-=1\n",
    "            nes[p0].append(p1)\n",
    "        kleft = [key for key, value in zy.items() if value  == 1]  \n",
    "        kk=pairs[0][0]\n",
    "        if kleft:\n",
    "            kk=kleft[0]       \n",
    "        dfs(kk)\n",
    "        l=len(rs)-1\n",
    "\n",
    "        \n",
    "        return [[rs[l-i],rs[l-i-1]] for i in range(l)]        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(pairs)\n",
    "\n",
    "        g = defaultdict(list)\n",
    "        ind = defaultdict(int)\n",
    "        od = defaultdict(int)\n",
    "\n",
    "        for a, b in pairs:\n",
    "            g[a].append(b)\n",
    "            ind[b] += 1\n",
    "            od[a] += 1\n",
    "\n",
    "        start = -1\n",
    "        for k in od:\n",
    "            if od[k] - ind[k] == 1 or start == -1:\n",
    "                start = k\n",
    "\n",
    "        print(start)\n",
    "\n",
    "        ret = []\n",
    "        def dfs(x):\n",
    "            while g[x]:\n",
    "                y = g[x].pop()\n",
    "                dfs(y)\n",
    "                ret.append((x, y))\n",
    "\n",
    "        dfs(start)\n",
    "        ret.reverse()\n",
    "\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:\n",
    "        g = defaultdict(list) \n",
    "        indeg = Counter() \n",
    "        outdeg = Counter() \n",
    "        for a, b in pairs:\n",
    "            g[a].append(b)\n",
    "            #g[b].append(a) \n",
    "            indeg[b] += 1\n",
    "            outdeg[a] += 1\n",
    "\n",
    "        start = pairs[0][0] \n",
    "        for x in outdeg:\n",
    "            if outdeg[x] == indeg[x] + 1:\n",
    "                start = x\n",
    "                break \n",
    "        ans = []\n",
    "        def dfs(u):\n",
    "            while g[u]:\n",
    "                v = g[u].pop() \n",
    "                dfs(v) \n",
    "                ans.append((u,v))\n",
    "        dfs(start) \n",
    "        return ans[::-1] \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:\n",
    "        from collections import defaultdict, Counter\n",
    "        edges = defaultdict(list)\n",
    "        indeg = Counter()\n",
    "        outdeg = Counter()\n",
    "        for x, y in pairs:\n",
    "            edges[x].append(y)\n",
    "            outdeg[x] += 1\n",
    "            indeg[y] += 1\n",
    "        \n",
    "        start = pairs[0][0]\n",
    "        for x in outdeg:\n",
    "            if outdeg[x] == indeg[x] + 1:\n",
    "                start = x\n",
    "                break\n",
    "        \n",
    "        res = []\n",
    "        def dfs(u):\n",
    "            while edges[u]:\n",
    "                v = edges[u].pop()\n",
    "                # res.append([u, v])\n",
    "                dfs(v)\n",
    "                res.append([u, v])\n",
    "        dfs(start)\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:\n",
    "        # 存储图\n",
    "        edges = defaultdict(list)\n",
    "        # 存储入度和出度\n",
    "        degree = Counter() \n",
    "        for x, y in pairs:\n",
    "            edges[x].append(y)\n",
    "            degree[y] -= 1\n",
    "            degree[x] += 1\n",
    "        \n",
    "        # 寻找起始节点\n",
    "        start = pairs[0][0]\n",
    "        for x in degree:\n",
    "            # 如果有节点出度比入度恰好多 1，那么只有它才能是起始节点\n",
    "            if degree[x] ==   1:\n",
    "                start = x\n",
    "                break\n",
    "        \n",
    "        ans = list()\n",
    "        \n",
    "        # 深度优先搜索（Hierholzer 算法）求解欧拉通路\n",
    "        def dfs(u: int) -> None:\n",
    "            while edges[u]:\n",
    "                v = edges[u].pop()\n",
    "                dfs(v)\n",
    "                ans.append([u, v])\n",
    "        \n",
    "        dfs(start)\n",
    "        return ans[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:\n",
    "        dcc, dc = defaultdict(int), defaultdict(list)\n",
    "        for i,j in pairs:\n",
    "            dcc[i] += 1\n",
    "            dcc[j] -= 1\n",
    "            dc[i].append(j)\n",
    "        start = pairs[0][0]\n",
    "        for i in dcc:\n",
    "            if dcc[i]==1:\n",
    "                start=i\n",
    "                break\n",
    "        res = []\n",
    "        def dfs(node):\n",
    "            while dc[node]:\n",
    "                nextnode = dc[node].pop()\n",
    "                dfs(nextnode)\n",
    "                res.append([node, nextnode])\n",
    "        dfs(start)\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:\n",
    "        g = defaultdict(list)\n",
    "        in_d = defaultdict(int)\n",
    "        out_d = defaultdict(int)\n",
    "        start = pairs[0][0]\n",
    "        for p1, p2 in pairs:\n",
    "            g[p1].append(p2)\n",
    "            in_d[p2] += 1\n",
    "            out_d[p1] += 1\n",
    "        for k, v in out_d.items():\n",
    "            if v == in_d[k] + 1:\n",
    "                start = k\n",
    "                break\n",
    "        def dfs(g, node, path, parent):\n",
    "            while g[node]:\n",
    "                nxt = g[node].pop()\n",
    "                dfs(g, nxt, path, node)\n",
    "            path.append(node)\n",
    "        path = []\n",
    "        dfs(g, start, path, -1)\n",
    "        ans = []\n",
    "        for i in range(len(path) - 1, 0, -1):\n",
    "            ans.append([path[i], path[i - 1]])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Graph:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.g = defaultdict(list)\n",
    "        self.o_d = defaultdict(int)\n",
    "        self.i_d = defaultdict(int)\n",
    "        self.n_edges = 0\n",
    "\n",
    "    def add_edge(self, u, v):\n",
    "        self.g[u].append(v)\n",
    "        self.g[v]\n",
    "        self.o_d[u] += 1\n",
    "        self.i_d[v] += 1\n",
    "        self.n_edges += 1\n",
    "\n",
    "    # 求欧拉路（欧拉通路或者欧拉回路）\n",
    "    # 图连通；除两个端点之外其余节点入度与出度相等；1个节点的入度比初度大1，1个节点的入度比出度小1。\n",
    "    def find_euler_path(self):\n",
    "        # 判断是否存在满足条件的起点和终点\n",
    "        start, end = None, None\n",
    "        for u in self.g:\n",
    "            if self.o_d[u] - self.i_d[u] == 1:  # 1个节点的出度比如度大1\n",
    "                if start is not None: return []  # 存在多个终点\n",
    "                start = u\n",
    "            elif self.i_d[u] - self.o_d[u] == 1:  # 1个节点的入度比出度大1\n",
    "                if end is not None: return []  # 存在多个终点\n",
    "                end = u\n",
    "            elif self.i_d[u] != self.o_d[u]:\n",
    "                return []  # 入度和出度不相等，无法找到满足条件的路径\n",
    "        if start is None or end is None:  # 无起点和终点，是欧拉回路，就随便找个起点即可\n",
    "            start = list(self.g.keys())[0]\n",
    "        # 深度优先搜索\n",
    "        path = []\n",
    "\n",
    "        def dfs(node):\n",
    "            while self.o_d[node] > 0:  # 出度大于0就可以继续走\n",
    "                self.o_d[node] -= 1\n",
    "                dfs(self.g[node].pop())\n",
    "            path.append(node)\n",
    "\n",
    "        dfs(start)\n",
    "        # 判断是否找到了有效的路径\n",
    "        if len(path) != self.n_edges + 1:\n",
    "            return []\n",
    "\n",
    "        return path[::-1]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:\n",
    "        # 欧拉通路的模板题\n",
    "        g = Graph()\n",
    "        for idx, (i, o) in enumerate(pairs):\n",
    "            g.add_edge(i, o)\n",
    "        return [[u, v] for u, v in pairwise(g.find_euler_path())]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:\n",
    "        # 显然是求一个欧拉路径就行了\n",
    "        # pairs 中不存在一模一样的数对。\n",
    "        # 题目已经保证是半欧拉图了，所以不需要验证，判断一下起点就完事\n",
    "        g = defaultdict(list)\n",
    "        ind = defaultdict(int)\n",
    "        for u, v in pairs:\n",
    "            ind[u] -= 1\n",
    "            ind[v] += 1\n",
    "            g[u].append(v)\n",
    "        \n",
    "        # 选择一个起点\n",
    "        start = -1\n",
    "        for k in ind:\n",
    "            if ind[k] == -1:\n",
    "                start = k\n",
    "                break\n",
    "        if start == -1:\n",
    "            start = k\n",
    "        \n",
    "        # 深搜解决问题\n",
    "        def dfs(x):\n",
    "            while g[x]:\n",
    "                dfs(g[x].pop())\n",
    "            ans.append(x)\n",
    "        \n",
    "        ans = []\n",
    "        dfs(start)\n",
    "        return [[x, y] for x, y in pairwise(ans[::-1])]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:\n",
    "        e=collections.defaultdict(list)\n",
    "        d=collections.Counter()\n",
    "        for a,b in pairs:\n",
    "            e[a].append(b)\n",
    "            d[a]+=1\n",
    "            d[b]-=1\n",
    "        start=-1\n",
    "        for key in d:\n",
    "            if d[key]>0:\n",
    "                start=key\n",
    "                break\n",
    "        if start==-1:\n",
    "            start=pairs[0][0]\n",
    "        ans=[]\n",
    "        def dfs(point):\n",
    "            while e[point]:\n",
    "                tp=e[point].pop()\n",
    "                dfs(tp)\n",
    "                ans.append([point,tp])\n",
    "        dfs(start)\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:\n",
    "        g = defaultdict(list)\n",
    "        incnt, outcnt = Counter(), Counter()\n",
    "        for s, e in pairs:\n",
    "            g[s].append(e)\n",
    "            outcnt[s] += 1\n",
    "            incnt[e] += 1\n",
    "        \n",
    "        start = pairs[0][0]\n",
    "        for x in outcnt:\n",
    "            if outcnt[x] == incnt[x] + 1:\n",
    "                start = x\n",
    "                break\n",
    "        \n",
    "        ans = []\n",
    "        def dfs(x: int):\n",
    "            while g[x]:\n",
    "                y = g[x].pop()\n",
    "                dfs(y)\n",
    "                ans.append((x, y))\n",
    "        \n",
    "        dfs(start)\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:\r\n",
    "        nes = defaultdict(list)\r\n",
    "        cnt = defaultdict(int)\r\n",
    "        for u, v in pairs:\r\n",
    "            nes[u].append(v)\r\n",
    "            cnt[u] += 1\r\n",
    "            cnt[v] -= 1\r\n",
    "        \r\n",
    "        st = pairs[0][0]\r\n",
    "        for node, c in cnt.items():\r\n",
    "            if c == 1:\r\n",
    "                st = node\r\n",
    "                break\r\n",
    "\r\n",
    "        pts = []\r\n",
    "        def dfs(node):\r\n",
    "            v = nes[node]\r\n",
    "            while len(v):\r\n",
    "                dfs(v.pop())\r\n",
    "            pts.append(node)\r\n",
    "\r\n",
    "        dfs(st)\r\n",
    "        \r\n",
    "        return [[pts[i], pts[i-1]] for i in range(len(pts) - 1, 0, -1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:\n",
    "        ind = collections.Counter()\n",
    "        graph = collections.defaultdict(list)\n",
    "        for a, b in pairs:\n",
    "            ind[a] -= 1 \n",
    "            ind[b] += 1 \n",
    "            graph[a].append(b)\n",
    "\n",
    "        start = pairs[0][0]\n",
    "        for c in ind:\n",
    "            if ind[c] == - 1:\n",
    "                start = c \n",
    "                break \n",
    "        res = []\n",
    "        def dfs(start):\n",
    "            while graph[start]:\n",
    "                nxt = graph[start].pop()\n",
    "                dfs(nxt)\n",
    "                res.append([start, nxt])\n",
    "        dfs(start)\n",
    "        return res[::-1]\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:\n",
    "        ind=collections.Counter()\n",
    "        oud=collections.Counter()\n",
    "        ad=collections.defaultdict(list)\n",
    "        for s,e in pairs:\n",
    "            oud[s]+=1\n",
    "            oud[e]+=0\n",
    "            ind[s]+=0\n",
    "            ind[e]+=1\n",
    "            ad[s].append(e)\n",
    "        \n",
    "        for x in ind:\n",
    "            start=x\n",
    "           # print(x,oud[x],ind[x])\n",
    "            if oud[x]-ind[x]==1:\n",
    "                break\n",
    "       # print(start)\n",
    "        ans=[]\n",
    "       # while \n",
    "        vis=set()\n",
    "       # vis.add(start)\n",
    "        def dfs(pre):\n",
    "            nonlocal ans\n",
    "            while ad[pre]:\n",
    "                nex=ad[pre].pop()\n",
    "                dfs(nex)\n",
    "                ans.append([pre,nex])\n",
    "            return \n",
    "        \n",
    "        #ans.append([pre,nex])\n",
    "      \n",
    "\n",
    "        dfs(start)\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:\n",
    "        ind=collections.Counter()\n",
    "        oud=collections.Counter()\n",
    "        ad=collections.defaultdict(list)\n",
    "        for s,e in pairs:\n",
    "            oud[s]+=1\n",
    "            oud[e]+=0\n",
    "            ind[s]+=0\n",
    "            ind[e]+=1\n",
    "            ad[s].append(e)\n",
    "        \n",
    "        for x in ind:\n",
    "            start=x\n",
    "           # print(x,oud[x],ind[x])\n",
    "            if oud[x]-ind[x]==1:\n",
    "                break\n",
    "       # print(start)\n",
    "        ans=[]\n",
    "        def dfs(pre):\n",
    "            nonlocal ans\n",
    "            while ad[pre]:\n",
    "                nex=ad[pre].pop()\n",
    "                dfs(nex)\n",
    "                ans.append([pre,nex])\n",
    "            return \n",
    "\n",
    "        dfs(start)\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:\n",
    "        edges = defaultdict(list)\n",
    "        pCnt, cCnt = Counter(), Counter()\n",
    "        for x, y in pairs:\n",
    "            edges[x].append(y)\n",
    "            pCnt[y] += 1\n",
    "            cCnt[x] += 1\n",
    "        \n",
    "       \n",
    "        start = pairs[0][0]\n",
    "        for x in cCnt:\n",
    "            if cCnt[x] == pCnt[x] + 1:\n",
    "                start = x\n",
    "                break\n",
    "        res = list()\n",
    "        \n",
    "        def dfs(u: int) -> None:\n",
    "            while edges[u]:\n",
    "                v = edges[u].pop()\n",
    "                dfs(v)\n",
    "                res.append([u, v])\n",
    "        \n",
    "        dfs(start)\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:\n",
    "        # 存储图\n",
    "        edges = defaultdict(list)\n",
    "        # 存储入度和出度\n",
    "        indeg, outdeg = Counter(), Counter()\n",
    "        for x, y in pairs:\n",
    "            edges[x].append(y)\n",
    "            indeg[y] += 1\n",
    "            outdeg[x] += 1\n",
    "        \n",
    "        # 寻找起始节点\n",
    "        start = pairs[0][0]\n",
    "        for x in outdeg:\n",
    "            # 如果有节点出度比入度恰好多 1，那么只有它才能是起始节点\n",
    "            if outdeg[x] == indeg[x] + 1:\n",
    "                start = x\n",
    "                break\n",
    "        \n",
    "        ans = list()\n",
    "        \n",
    "        # 深度优先搜索（Hierholzer 算法）求解欧拉通路\n",
    "        def dfs(u: int) -> None:\n",
    "            while edges[u]:\n",
    "                v = edges[u].pop()\n",
    "                dfs(v)\n",
    "                ans.append([u, v])\n",
    "        \n",
    "        dfs(start)\n",
    "        return ans[::-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:\n",
    "        # 存储图\n",
    "        edges = defaultdict(list)\n",
    "        # 存储入度和出度\n",
    "        indeg, outdeg = Counter(), Counter()\n",
    "        for x, y in pairs:\n",
    "            edges[x].append(y)\n",
    "            indeg[y] += 1\n",
    "            outdeg[x] += 1\n",
    "        \n",
    "        # 寻找起始节点\n",
    "        start = pairs[0][0]\n",
    "        for x in outdeg:\n",
    "            # 如果有节点出度比入度恰好多 1，那么只有它才能是起始节点\n",
    "            if outdeg[x] == indeg[x] + 1:\n",
    "                start = x\n",
    "                break\n",
    "        \n",
    "        ans = list()\n",
    "        \n",
    "        # 深度优先搜索（Hierholzer 算法）求解欧拉通路\n",
    "        def dfs(u: int) -> None:\n",
    "            while edges[u]:\n",
    "                v = edges[u].pop()\n",
    "                dfs(v)\n",
    "                ans.append([u, v])\n",
    "        \n",
    "        dfs(start)\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:\n",
    "        # 存储图\n",
    "        edges = defaultdict(list)\n",
    "        # 存储入度和出度\n",
    "        indeg, outdeg = Counter(), Counter()\n",
    "        for x, y in pairs:\n",
    "            edges[x].append(y)\n",
    "            indeg[y] += 1\n",
    "            outdeg[x] += 1\n",
    "        \n",
    "        # 寻找起始节点\n",
    "        start = pairs[0][0]\n",
    "        for x in outdeg:\n",
    "            # 如果有节点出度比入度恰好多 1，那么只有它才能是起始节点\n",
    "            if outdeg[x] == indeg[x] + 1:\n",
    "                start = x\n",
    "                break\n",
    "        \n",
    "        ans = list()\n",
    "        \n",
    "        # 深度优先搜索（Hierholzer 算法）求解欧拉通路\n",
    "        def dfs(u: int) -> None:\n",
    "            while edges[u]:\n",
    "                v = edges[u].pop()\n",
    "                dfs(v)\n",
    "                ans.append([u, v])\n",
    "        \n",
    "        dfs(start)\n",
    "        return ans[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:\r\n",
    "        # def validArrangement(self, pairs):\r\n",
    "        '''\r\n",
    "        1. 构建图（将给定的数组表示一条有向边，两端点表示两节点）\r\n",
    "        2. 深度搜索所有边（欧拉通路--起始搜索点|出度-入度| == 1）\r\n",
    "        '''\r\n",
    "        N = len(pairs)\r\n",
    "        edges = {}\r\n",
    "        in_node, out_node = {}, {}\r\n",
    "        for i in range(N):\r\n",
    "            edges.setdefault(pairs[i][0], [])\r\n",
    "            edges[pairs[i][0]].append(pairs[i][1])\r\n",
    "            out_node[pairs[i][0]] = out_node.setdefault(pairs[i][0], 0) + 1\r\n",
    "            in_node[pairs[i][1]] = in_node.setdefault(pairs[i][1], 0) + 1\r\n",
    "\r\n",
    "        first_node = None\r\n",
    "        # 确定初始搜索节点\r\n",
    "        for i in edges:\r\n",
    "            if out_node.setdefault(i, 0) - in_node.setdefault(i, 0) == 1:\r\n",
    "                first_node = i\r\n",
    "                break\r\n",
    "            elif out_node.setdefault(i, 0) - in_node.setdefault(i, 0) == 0:\r\n",
    "                first_node = i\r\n",
    "\r\n",
    "        res = []\r\n",
    "\r\n",
    "        def dfs(n) -> None:\r\n",
    "            while edges.setdefault(n, []):\r\n",
    "                t = edges[n].pop()\r\n",
    "                dfs(t)\r\n",
    "                res.append([n, t])\r\n",
    "            # return 0\r\n",
    "        dfs(first_node)\r\n",
    "        return res[::-1]\r\n",
    "        # print('this node path')\r\n",
    "        # print(node_path)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# File       : Q2097.py\n",
    "# Time       ：2023/9/20 14:57\n",
    "# Author     ：author name\n",
    "# version    ：python 3\n",
    "# Description：\n",
    "\"\"\"\n",
    "\n",
    "\"\"\"\n",
    "2097. 合法重新排列数对\n",
    "提示\n",
    "困难\n",
    "45\n",
    "相关企业\n",
    "给你一个下标从 0 开始的二维整数数组 pairs ，其中 pairs[i] = [starti, endi] 。如果 pairs 的一个重新排列，满足对每一个下标 i （ 1 <= i < pairs.length ）都有 endi-1 == starti ，那么我们就认为这个重新排列是 pairs 的一个 合法重新排列 。\n",
    "\n",
    "请你返回 任意一个 pairs 的合法重新排列。\n",
    "\n",
    "注意：数据保证至少存在一个 pairs 的合法重新排列。\n",
    "\n",
    " \n",
    "\n",
    "示例 1：\n",
    "\n",
    "输入：pairs = [[5,1],[4,5],[11,9],[9,4]]\n",
    "输出：[[11,9],[9,4],[4,5],[5,1]]\n",
    "解释：\n",
    "输出的是一个合法重新排列，因为每一个 endi-1 都等于 starti 。\n",
    "end0 = 9 == 9 = start1 \n",
    "end1 = 4 == 4 = start2\n",
    "end2 = 5 == 5 = start3\n",
    "示例 2：\n",
    "\n",
    "输入：pairs = [[1,3],[3,2],[2,1]]\n",
    "输出：[[1,3],[3,2],[2,1]]\n",
    "解释：\n",
    "输出的是一个合法重新排列，因为每一个 endi-1 都等于 starti 。\n",
    "end0 = 3 == 3 = start1\n",
    "end1 = 2 == 2 = start2\n",
    "重新排列后的数组 [[2,1],[1,3],[3,2]] 和 [[3,2],[2,1],[1,3]] 都是合法的。\n",
    "示例 3：\n",
    "\n",
    "输入：pairs = [[1,2],[1,3],[2,1]]\n",
    "输出：[[1,2],[2,1],[1,3]]\n",
    "解释：\n",
    "输出的是一个合法重新排列，因为每一个 endi-1 都等于 starti 。\n",
    "end0 = 2 == 2 = start1\n",
    "end1 = 1 == 1 = start2\n",
    " \n",
    "\n",
    "提示：\n",
    "\n",
    "1 <= pairs.length <= 105\n",
    "pairs[i].length == 2\n",
    "0 <= starti, endi <= 109\n",
    "starti != endi\n",
    "pairs 中不存在一模一样的数对。\n",
    "至少 存在 一个合法的 pairs 重新排列。\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:\n",
    "        edges = defaultdict(list)\n",
    "\n",
    "        #存储入度和出度\n",
    "        indeg, outdeg = Counter(), Counter()\n",
    "        for k, v in pairs:\n",
    "            edges[k].append(v)\n",
    "            indeg[v] += 1\n",
    "            outdeg[k] += 1\n",
    "\n",
    "        #寻找起点\n",
    "        start = pairs[0][0]\n",
    "        for x in outdeg:\n",
    "            if outdeg[x] == indeg[x] + 1:\n",
    "                start = x\n",
    "                break\n",
    "\n",
    "        ans = list()\n",
    "        #dfs求解欧拉通路\n",
    "        def dfs(node):\n",
    "            while edges[node]:\n",
    "                v = edges[node].pop()\n",
    "                dfs(v)\n",
    "                ans.append([node, v])\n",
    "\n",
    "        dfs(start)\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:\n",
    "        # 题目保证时通路或者回路\n",
    "        # 1.通过入度，出度，判断是通路还是回路，找起点\n",
    "        indegree=defaultdict(int)\n",
    "        outdegree=defaultdict(int)\n",
    "        table=defaultdict(list)\n",
    "        node=set()\n",
    "        for start,end in pairs:\n",
    "            indegree[end]+=1\n",
    "            outdegree[start]+=1\n",
    "            table[start].append(end)\n",
    "            node.add(start)\n",
    "            node.add(end)\n",
    "        start=-1\n",
    "        for k in node:\n",
    "            if outdegree[k]-indegree[k]==1:\n",
    "                start=k\n",
    "                break\n",
    "        if start==-1:\n",
    "            start=pairs[0][0]\n",
    "        path=[]\n",
    "        def dfs(s):\n",
    "            while table[s]:\n",
    "                t=table[s].pop()\n",
    "                dfs(t)\n",
    "            path.append(s)\n",
    "        dfs(start)\n",
    "        path=path[::-1]\n",
    "        ans=[]\n",
    "        for i in range(len(path)-1):\n",
    "            ans.append(path[i:i+2])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:\n",
    "        g = defaultdict(list)\n",
    "        indeg, outdeg = Counter(), Counter()\n",
    "        for x, y in pairs:\n",
    "            g[x].append(y)\n",
    "            indeg[y] += 1\n",
    "            outdeg[x] += 1\n",
    "        \n",
    "        start = pairs[0][0]\n",
    "        for x in outdeg:\n",
    "            if outdeg[x] == indeg[x] + 1:\n",
    "                start = x\n",
    "                break\n",
    "        ans = []\n",
    "        def dfs(u: int) -> None:\n",
    "            while g[u]:\n",
    "                v = g[u].pop()\n",
    "                dfs(v)\n",
    "                ans.append([u, v])\n",
    "                \n",
    "        dfs(start)\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:\n",
    "        vec = defaultdict(list)\n",
    "        indeg, outdeg = Counter(), Counter()\n",
    "        for l, r in pairs:\n",
    "            indeg[r] += 1\n",
    "            outdeg[l] += 1\n",
    "            vec[l].append(r)\n",
    "        \n",
    "        start = pairs[0][0]\n",
    "        for k, _ in pairs:\n",
    "            if indeg[k] == outdeg[k] - 1:\n",
    "                start = k\n",
    "                break\n",
    "        \n",
    "        res = []\n",
    "        def dfs(cur):\n",
    "            while vec[cur]:\n",
    "                temp = vec[cur].pop()\n",
    "                dfs(temp)\n",
    "                res.append([cur, temp])\n",
    "        \n",
    "        dfs(start)\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:\n",
    "        ind=collections.Counter()\n",
    "        oud=collections.Counter()\n",
    "        ad=collections.defaultdict(list)\n",
    "        for s,e in pairs:\n",
    "            oud[s]+=1\n",
    "            oud[e]+=0\n",
    "            ind[s]+=0\n",
    "            ind[e]+=1\n",
    "            ad[s].append(e)\n",
    "        \n",
    "        for x in ind:\n",
    "            start=x\n",
    "            print(x,oud[x],ind[x])\n",
    "            if oud[x]-ind[x]==1:\n",
    "                start=x\n",
    "                break\n",
    "        print(start)\n",
    "        ans=[]\n",
    "        def dfs(pre):\n",
    "            nonlocal ans\n",
    "            while ad[pre]:\n",
    "                nex=ad[pre].pop()\n",
    "                dfs(nex)\n",
    "                ans.append([pre,nex])\n",
    "            return \n",
    "\n",
    "        dfs(start)\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:\n",
    "        # 题目保证时通路或者回路\n",
    "        # 1.通过入度，出度，判断是通路还是回路，找起点\n",
    "        indegree=defaultdict(int)\n",
    "        outdegree=defaultdict(int)\n",
    "        table=defaultdict(list)\n",
    "        node=set()\n",
    "        for start,end in pairs:\n",
    "            indegree[end]+=1\n",
    "            outdegree[start]+=1\n",
    "            table[start].append(end)\n",
    "            node.add(start)\n",
    "            node.add(end)\n",
    "        start=pairs[0][0]\n",
    "        for k in node:\n",
    "            if outdegree[k]-indegree[k]==1:\n",
    "                start=k\n",
    "                break\n",
    "        ans=[]\n",
    "        def dfs(s):\n",
    "            while table[s]:\n",
    "                t=table[s].pop()\n",
    "                dfs(t)\n",
    "                ans.append([s,t])\n",
    "        dfs(start)\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:\n",
    "        # 存顶点的出入度\n",
    "        degree = defaultdict(lambda: [0, 0])\n",
    "        # 存储图关系\n",
    "        edge = defaultdict(list)\n",
    "        for i, j in pairs:\n",
    "            degree[i][0] += 1\n",
    "            degree[j][1] += 1\n",
    "            edge[i].append(j)\n",
    "\n",
    "        # 寻找起始节点\n",
    "        start = pairs[0][0]\n",
    "        for i in degree:\n",
    "            # 如果有节点出度比入度恰好多 1，那么只有它才能是起始节点\n",
    "            if degree[i][0] - degree[i][1] == 1:\n",
    "                start = i\n",
    "                break\n",
    "\n",
    "        def dfs(pre):\n",
    "            # 深度优先搜索（Hierholzer 算法）求解欧拉通路\n",
    "            while edge[pre]:\n",
    "                nex = edge[pre].pop()\n",
    "                dfs(nex)\n",
    "                ans.append([pre, nex])\n",
    "            return\n",
    "\n",
    "        ans = list()\n",
    "        dfs(start)\n",
    "        return ans[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:\n",
    "        # 存储图\n",
    "        edges = defaultdict(list)\n",
    "        # 存储入度和出度\n",
    "        indeg, outdeg = Counter(), Counter()\n",
    "        for x, y in pairs:\n",
    "            edges[x].append(y)\n",
    "            indeg[y] += 1\n",
    "            outdeg[x] += 1\n",
    "        \n",
    "        # 寻找起始节点\n",
    "        start = pairs[0][0]\n",
    "        for x in outdeg:\n",
    "            # 如果有节点出度比入度恰好多 1，那么只有它才能是起始节点\n",
    "            if outdeg[x] == indeg[x] + 1:\n",
    "                start = x\n",
    "                break\n",
    "        \n",
    "        ans = list()\n",
    "        \n",
    "        # 深度优先搜索（Hierholzer 算法）求解欧拉通路\n",
    "        def dfs(u):\n",
    "            while edges[u]:\n",
    "                v = edges[u].pop()\n",
    "                dfs(v)\n",
    "                ans.append([u, v])\n",
    "        \n",
    "        dfs(start)\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:\n",
    "        def dfs(u):\n",
    "            if u in mp:\n",
    "                while len(mp[u]) > 0:\n",
    "                    v = mp[u].pop()\n",
    "                    dfs(v)\n",
    "            ans.append(u)\n",
    "            \n",
    "        ans = []\n",
    "        mp = dict()\n",
    "        cnt_in = dict()\n",
    "        cnt_out = dict()\n",
    "        for a, b in pairs:\n",
    "            if a in mp:\n",
    "                mp[a].add(b)\n",
    "                cnt_out[a] += 1\n",
    "            else:\n",
    "                mp[a] = set()\n",
    "                mp[a].add(b)\n",
    "                cnt_out[a] = 1\n",
    "\n",
    "            if b in cnt_in:\n",
    "                cnt_in[b] += 1\n",
    "            else:\n",
    "                cnt_in[b] = 1\n",
    "        \n",
    "        start = None\n",
    "        for k in cnt_out.keys():\n",
    "            if (k in cnt_out and k not in cnt_in) or (cnt_out[k] - cnt_in[k] == 1):\n",
    "                if start is None:\n",
    "                    start = k\n",
    "                else:\n",
    "                    start = min(start, k)\n",
    "                break\n",
    "        if start is None:\n",
    "            for k in cnt_out.keys():\n",
    "                if start is None:\n",
    "                    start = k\n",
    "                else:\n",
    "                    start = min(start, k)\n",
    "                break\n",
    "        dfs(start)\n",
    "        ans.reverse()        \n",
    "        \n",
    "        res = []\n",
    "        for i in range(len(ans)-1):\n",
    "            res.append([ans[i], ans[i+1]])\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:\n",
    "        def dfs(u):\n",
    "            if u in mp:\n",
    "                while len(mp[u]) > 0:\n",
    "                    v = mp[u].pop()\n",
    "                    dfs(v)\n",
    "            ans.append(u)\n",
    "            \n",
    "        ans = []\n",
    "        mp = dict()\n",
    "        cnt_in = dict()\n",
    "        cnt_out = dict()\n",
    "        for a, b in pairs:\n",
    "            if a in mp:\n",
    "                mp[a].add(b)\n",
    "                cnt_out[a] += 1\n",
    "            else:\n",
    "                mp[a] = set()\n",
    "                mp[a].add(b)\n",
    "                cnt_out[a] = 1\n",
    "\n",
    "            if b in cnt_in:\n",
    "                cnt_in[b] += 1\n",
    "            else:\n",
    "                cnt_in[b] = 1\n",
    "        \n",
    "        start = None\n",
    "        for k in cnt_out.keys():\n",
    "            if (k in cnt_out and k not in cnt_in) or (cnt_out[k] - cnt_in[k] == 1):\n",
    "                start = k\n",
    "                break\n",
    "        if start is None:\n",
    "            for k in cnt_out.keys():\n",
    "                start = k\n",
    "                break\n",
    "        dfs(start)\n",
    "        ans.reverse()        \n",
    "        \n",
    "        res = []\n",
    "        for i in range(len(ans)-1):\n",
    "            res.append([ans[i], ans[i+1]])\n",
    "\n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
